1. Field of the Invention
This invention relates to the calculation of discrete cosine transforms and inverse discrete cosine transforms, which are useful in signal processing. In particular, the invention relates to using an adder network for speedy calculations and economical hardware design.
2. Description of Related Art
The discrete cosine transform (DCT) is important to digital signal processing, as standards for compression of both still and video images incorporate the DCT transform and speech coding sometimes also relies on the DCT transform. Products that rely on DCT and the reciprocal inverse discrete cosine transform (IDCT) may include definition TV (HDTV), video conferencing, digital cameras and voice compression and recognition systems. The Joint Photographic Expert Group adopted a standard for compression of still images in 1992, known as JPEG. The Moving Picture Experts Group (MPEG) of the International Organization for Standardization (ISO) has adopted or published for comment a series of standards for video compression (e.g., MPEG-2, MPEG-4, etc.) In the United States and elsewhere, standards have emerged for high definition TV (HDTV). Common to these standards is use of DCT/IDCT for data compression scheme. As DCT also is used for speech coding, its application is not limited to image data.
Several favorable mathematical properties of DCT have led to its adoption for data compression and analysis. It is real, separable, orthogonal, and approximates the statistically optimal Karhunen-Loeve transform. When factored, the DCT transform matrix contains many zeros: submaticies in the upper left and lower right quadrants of the matrix have real values and the upper right and lower left quadrants are zeros.   (            E      .      g      .        ,                  [                                                            C                ⁢                                                                   ⁢                e                                                    0                                                          0                                                      C                ⁢                                                                   ⁢                o                                                    ]            .        )The separability property allows a two dimensional DCT to be calculated by repeated application of a one dimensional transform. For data compression, when output values are quantized and zig-zag or otherwise reordered, run length encoding or other data compression schemes can productively be applied.
Rao & Yip explain in their book Discrete Cosine Transform Algorithms, Advantages, Application (Academic Press 1990), the DCT transform was not discovered until 1974. The evolution of DCT chips only began in 1984. A substantial amount of effort has been devoted to implementing DCT in hardware. Much work has been devoted to distributed arithmetic implementations. Rao & Yip describe several distributed arithmetic devices in section 5.6 of their book. The U.S. Pat. No. 5,805,482 issued to Larry Phillips is for an improved distributed arithmetic device. An article by Roger Woods, David Trainor & Jean-Paul Heron, Applying an XC6200 to Real-Time Image Processing, IEEE Design & Test of Computers, p. 30 (January-March 1998) also applies distributed arithmetic to 2-D DCT transforms.
An adder network is an alternative to distributed arithmetic which exploits the cyclic convolution property of the DCT/IDCT transform. Speed and economical hardware implementation are advantages of an adder network.